Date: Tue, 10 Dec 1996 14:54:46 GMT
Server: NCSA/1.4.2
Content-type: text/html
Last-modified: Wed, 27 Nov 1996 21:53:13 GMT
Content-length: 16744

<html>
<head>
<TITLE>
Papers of Richard E. Ladner
</TITLE>
</head>
<body>
<h1>
Papers of Richard E. Ladner
</h1>
<H3>
Recent On-Line Papers
</H3>
The following are the most current versions of some of my
articles.  All papers are in postscript format (or compressed postscript).
You can also browse the departmental 
<a href=/research/tr/techreports.shtml> technical reports</a>.

<ul>


<li>
<a href=ftp://ftp.cs.washington.edu/tr/1996/10/UW-CSE-96-10-01.PS.Z>
<b>The Influence of Caches on the Performance of Sorting.</b></a>
A. LaMarca and R.E. Ladner.  This paper will appear in the Proceedings
of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms,
January, 1997.
<p>
<li>
<a href=ftp://ftp.cs.washington.edu/tr/1996/09/UW-CSE-96-09-02.PS.Z>
<b>Sorting by Parallel Insertion on a One-Dimensional
     Sub-Bus Array.</b></a>
J.D. Fix and R.E. Ladner.  This paper was recently submitted for
publication.
<p>
<li>
<a href=ftp://ftp.cs.washington.edu/tr/1996/02/UW-CSE-96-02-03.PS.Z>
<b>The Influence of Caches on the Performance of Heaps.</b></a>
A. LaMarca and R.E. Ladner.  This paper was recently accepted to
ACM Journal of Applied Algorithmics.
<p>

<li>
<a href=ftp://ftp.cs.washington.edu/tr/1994/11/UW-CSE-94-11-01.PS.Z>
<b>Optimal One-Way Sorting on a One-Dimensional Sub-Bus Array.</b></a>
J. Fix and R.E Ladner.  This paper appeared in
Sixth Annual ACM-SIAM Symposium on Discrete Algorithms,
January, 1995, 586-594.

<p>

<li>
<a href=ftp://ftp.cs.washington.edu/tr/1994/09/UW-CSE-94-09-02.PS.Z>
<b>Optimizing Static Calendar Queues.</b></a>
K.B. Erickson, R.E. Ladner, and A. LaMarca. This paper appeared in
35th Annual Symposium on Foundations of Computer Science, November, 1994,
732-743, .
<p>

<li>
<a href=ftp://ftp.cs.washington.edu/tr/1993/10/UW-CSE-93-10-02.PS.Z>
<b>Complexity of Sub-Bus Mesh Computations.</b></a>
A. Condon, R. Ladner, J. Lampe, and R. Sinha.  This paper appeared in
<EM> SIAM Journal on Computing</EM>, Vol. 25, No. 3, 1996, 520-539.

<p> 

<li>
<a href=ftp://ftp.cs.washington.edu/tr/1993/04/UW-CSE-93-04-09.PS.Z>
<b>Building Counting Networks from Larger Balancers.</b></a>
E.W. Felten, A.  LaMarca, and R.E Ladner.  This paper is a Department of
Computer Science and Engineering, University of Washington Technical
Report TR 93-04-09.
<p>

<li>
<a href=ftp://ftp.cs.washington.edu/tr/1992/12/UW-CSE-92-12-08.PS.Z>
<b>Theory and Practice of Vector Quantizers Trained on Small
Training Sets.</b></a>
D. Cohn, E.A. Riskin, and R.Ladner.  This paper appeared
<EM> IEEE Transactions on Pattern Analysis and
  Machine Intelligence</EM>,Vol. 16, 1994, 54-65.

<p>

</ul>


</body>

</html>

<H3>
Papers in Refereed Journals
</H3>

<UL>
<LI>
A. LaMarca and R.E. Ladner.
The Influence of Caches on the Performance of Heaps.
To appear in the <EM> Journal of Applied Algorithmics</EM>.

<LI> 
R.-Y. Wang, E.A. Riskin, and R. Ladner.
Codebook Organization to Enhance Maximum A Posteriori Detection
of Progressive Transmission of Vector Quantized Images over Noisy
Channels.
<EM> IEEE Transactions on Image Processing</EM>, Vol. 5, No. 1, 1996, 37-48.

<LI> A. Condon, R.E. Ladner, J. Lampe, and R. Sinha.
Complexity of Sub-Bus Mesh Computations. 
<EM> SIAM Journal on Computing</EM>, Vol. 25, No. 3, 1996, 520-539.

<LI> E. Tempero and R. Ladner.  Recoverable Sequence Transmission
Protocols. 
<EM> Journal of the ACM</EM>, Vol. 42, No. 5, 1995, 1059-1090.

<LI> A. Condon and R. Ladner. Interactive Proof Systems with
Polynomial Bounded Strategies. 
<EM> Journal of Computer and Systems Sciences, Vol. 50</EM>, 1995, 506-518.

<LI> E.A. Riskin, R. Ladner, L.E., R.Y. Wang, and L.E. Atlas.
Index Assignment for Progressive Transmission of Full Search Vector
Quantization.  Correspondence in <EM> IEEE Transactions on Image Processing</EM>
Vol. 3, No. 3 1994, 307-312.

<LI> D. Cohn. E.A. Riskin, R. Ladner. Theory and 
Practice of Vector Quantizers Trained on Small Training Sets.
<EM> IEEE Transactions on Pattern Analysis and
  Machine Intelligence</EM>,Vol. 16, 1994, 54-65.

<LI> D. Cohn, L. Atlas, R. Ladner. Improving Generalization with
Self-Directed Learning.  <EM> Machine Learning</EM>, Vol. 15, 1994, 201-221.

<LI> P. Beame, E. Brisson, and R.E. Ladner. The Complexity of
Computing Symmetric Functions Using Threshold Circuits. 
<EM> Theoretical Computer Science, Vol. 100</EM>, 1992, 253-265.
        
<LI> S. Chaudhuri and R.E. Ladner. Safety and Liveness of
$\omega$-Context-Free Languages. 
<EM> Information Processing Letters, Vol. 37</EM>, 1991, 13-20.

<LI> R.E. Ladner, Polynomial Space Counting Problems. 
<EM> SIAM Journal on Computing, Vol. 18</EM>, December 1989, 1087-1097.

<LI> R.E. Ladner, Computer Accessibility for Federal Workers with
Disabilities: It's the Law. 
<EM> Communications of the ACM, Vol. 32, No. 8</EM>, August, 1989, 952-956.

<LI> A. Condon and R.E. Ladner, Probabilistic Game Automata.
<EM> Journal of Computer and System Sciences, Vol. 36. No. 3</EM>,
June 1988, 452-489

<LI> A.G. Greenberg, P. Flajolet, R.E. Ladner, Estimating the
Multiplicities of Conflicts to Speed Their Resolution in Multiple
Access Channels. <EM> Journal of the ACM, Vol. 34, No. 2</EM>, April 1987,
289-325

<LI> R.E. Ladner and J. K. Norman, Solitaire Automata,
<EM> Journal of Computer and System Sciences, Vol. 30, No. 1</EM>, February 1985,
116-129

<LI> R. E. Ladner, L. J. Stockmeyer, and R. J. Lipton, Alternation Bounded
Auxiliary Pushdown Automata. <EM> Information and Control, Vol. 62, Nos. 2/3</EM>,
August/September 1984, 93-108

<LI> U. Manber and R.E. Ladner, Concurrency Control in a Dynamic Search
Structure. <EM> ACM Transactions on Database Systems, vol. 9, no. 3.</EM> September
1984, 439-455

<LI> E. P. Glinert and R. E. Ladner, A Large Font Virtual Terminal Interface -
A Software Prosthesis for the Visually Impaired.
<EM> Communications of the ACM, vol. 27, no. 6</EM>, June 1984, 567-572

<LI> V. Klee, R. E. Ladner, and R. Manber, Signsolvability Revisited.
<EM> Linear Algebra and Its Applications vol. 59</EM>, 1984, 131-157

<LI> R. E. Ladner, R. J. Lipton, L. J. Stockmeyer, Alternating
Pushdown and Stack Automata.  <EM> SIAM Journal on Computing, vol. 13, no. 1</EM>,
February 1984, 135-155

<LI> J.-L. Baer, H. C. Du, and R. E. Ladner, Binary Search 
in a Multiprocessing
Environment. <EM> IEEE Transactions on Computers, vol. c-32, no.7</EM>, July 1983,
667-677

<LI> A. G. Greenberg, R. E. Ladner, M. S. Paterson, and Z. Galil, 
Efficient Parallel Algorithms for Linear Recurrence Computation.
<EM> Information Processing Letters, vol. 15, no. 1</EM>, August 1982, 31-35

<LI> R. E. Ladner, The Complexity of Problems in Systems of
Communicating Sequential Processes. <EM> Journal of
Computer and System Sciences, vol. 21, no.2</EM>, October 1980, 179-194

<LI> R. E. Ladner and M. J. Fischer, Parallel Prefix Computation.
<EM> Journal of the ACM, vol. 27, no. 4</EM>, October 1980, 831-838

<LI> P. Honeyman, R. E. Ladner, and M. Yannakakis, Testing the
Universal Instance Assumption. <EM> Information Processing Letters,
vol. 10, no. 1</EM>, February l980, 14-19

<LI> M. J. Fischer and R. E. Ladner, Propositional Dynamic Logic
of Regular Programs. <EM> Journal of Computer and System Sciences,
vol. 18, no. 2</EM>, April 1979, 194-211

<LI> R. E. Ladner, The Computational Complexity of Provability
in Systems of Modal Propositional Logic. <EM> SIAM Journal on
Computing, vol. 6, no. 3</EM>, September 1977, 467-480

<LI> R. E. Ladner, Application of Model Theoretic Games to
Discrete Linear Orders and Finite Automata. <EM> Information and
Control, vol. 33, no. 4</EM>, April 1977, 281-303

<LI> R. E. Ladner and N. A. Lynch, Relativization of Questions
about Log Space Computability. <EM> Mathematical Systems Theory,
vol. 10, no. 1</EM>, 1976, 19-32

<LI> R. E. Ladner, N. A. Lynch and A. L. Selman, A Comparison of
Polynomial Time Reducibilities. <EM> Theoretical Computer Science,
vol. 1</EM>, 1975, 103-123

<LI> A. R. Freedman and R. E. Ladner, Space Bounds for Processing
Contentless Inputs. <EM> Journal of Computer and System Sciences,
vol. 11, no. 1</EM>, August 1975, 118-128

<LI> R. E. Ladner and L. P. Sasso, Jr., The Weak Truth Table Degrees
of Recursively Enumerable Sets. <EM> Annals of Mathematical Logic,
vol. 8</EM>, 1975, 429-448

<LI> R. E. Ladner, On the Structure of Polynomial Time Reducibility.
<EM> Journal of the ACM, vol. 22, no. 1</EM>, January 1975, 155-171

<LI> R. E. Ladner, A Completely Mitotic Nonrecursive R.E. Degree.
<EM> Transactions of the AMS, vol. 184</EM>, October 1973, 479-507

<LI> R. E. Ladner, Mitotic Recursively Enumerable Sets,
<EM> Journal of Symbolic Logic, vol. 38, no. 2</EM>, June, 1973,
199-211

</UL>

<H3>
Conference Papers
</H3>

<UL>
<LI>
A. LaMarca and R.E. Ladner.
The Influence of Caches on the Performance of Sorting.
Symposium on Discrete Algorithms. 1997.

<LI>
M.H. Johnson, R. Ladner, and E.A. Riskin.
Fast Nearest Neighbor Search for ECVQ and other Modified Distorsion 
Measures by Comparing Boundary Distance.
IEEE International Conference on Image Processing, 1996.

<LI>	
B.S. Srinivas, M. Azizoglu, E. Riskin and R. Ladner.
Progressive Image Transmission with Error Concealment on a Lossy
Packet Network. International Conference on Acoustics, 
Speech and Signal Processing, 1996.

<LI>
B.S. Srinivas, E.A. Riskin, R. Ladner and M. Azi\~{0}oglu.
Progressive Image Transmission on a Channel with Memory.
Thirty-third Annual
Allerton Conference on Communications, Control and Computing, 
pp. 265-274, Oct. 4-6th 1995.

<LI>
J.D. Fix and R.E. Ladner.
Optimal One-Way Sorting on a One-Dimensional Sub-Bus Array.
Sixth Annual ACM-SIAM Symposium on Discrete Algorithms,
January, 1995, 586-594.

<LI> K.B Erickson, R.E. Ladner, A. LaMarca.
Optimizing Static Calendar Queues.
35th Annual Symposium on Foundations of Computer Science, November, 1994
732-743.

<LI> R.E. Ladner, J. Lampe, and R. Rogers.
Vector Prefix Addition on Sub-Bus Mesh Computers. 1993
5th Annual ACM Symposium on Parallel Algorithms and Architectures

<LI> E.A. Riskin, R. Ladner, L.E. Atlas, and R.Y. Wang.
Index Assignment for Progressive Transmission of Full Search Vector
Quantization.  IEEE 1993 International Symposium on Information
Theory.  Later revised and published

<LI> D. Cohn, E.A. Riskin, and R. Ladner. Theory and Practice of
Vector Quantizers Trained on Small Training Sets.
IEEE 1993 International Symposium on Information
Theory.  Revised and published

<LI> A. Condon and R. Ladner. Interactive Proof Systems with
Polynomial Bounded Strategies. 1992 IEEE Conference on Structure
in Complexity Theory. Later revised and published

<LI> J. Felsenstein, R. Ladner, J. Lampe, and T. Nguyen.
Parallel Algorithms for Computational Biology (Extended Abstract).
Data Parallel Research Initiative Symposium sponsored by Digital
Equipment Corporation, April 1992.

<LI> E. Tempero and R.E. Ladner. Tight Bounds for Weakly-Bounded
Protocols. Ninth Annual ACM Symposium on Principles of Distributed
Computing, 1990, 205-218.  Revised and submitted for publication
under the title ``Recoverable Sequence Transmission Protocols''

<LI> D. Cohn, L. Atlas, R. Ladner, R. Marks II, M. El-Sharkawi,
M. Aggoune, D. Park. Training Connectionist Networks with Queries and
Selective Sampling. Advances in Neural Information Processing, 1989,
Edited by David S. Touretzky, Morgan Kaufmann Publishers, San
Mateo, CA. 566-573.  Part revised and published

<LI> R.E. Ladner. Computer Accessibility for Workers with Disabilities:
It's the Law. Invited Paper at DIAC-88, Directions and Implications of
Advanced Computing, August 1988, 18-23. Later revised and published

<LI> R. Ladner. DBNet - A Computer Network for Deaf-Blind People.
Computer Technology/Special Education/Rehabilitation
(Sponsored by Office of Disabled Student Services, California
State University, Northridge. October 1987, 349-356

<LI> R. Ladner, R. Day, D. Gentry, K. Meyer, and S. Rose.
A User Interface for Deaf-Blind People (Preliminary Report).
CHI+GI '87, Conference on Human Factors in Computing and Graphics 
Interface, April, 1987, 

<LI> A. Condon and R. Ladner, Probabilistic Game Automata.
Structure in Complexity Theory, Proceedings of the Conference held at
the University of California, June 1986.  Springer-Verlag Lecture Notes
in Computer Science, 223, 144-162. Later revised and published

<LI> R.E. Ladner and J. Reif, The Logic of Distributed Protocols.
Theoretical Aspects of Reasoning about Knowledge, Proceedings of the
1986 Conference.  Edited by Joseph Y. Halpern. Morgan Kaufmann 
Publishers, Inc. March 1986, 207-222

<LI> R.E. Ladner,  DBNet - A Computer Network for Deaf-Blind People. 10th 
University Study Conference (Sponsored by IBM), November 1985, 225-235

<LI> R. E. Ladner and B. J. Wagreich, Networks for Deaf-Blind People. 
Spring COMPCON '84, February, 1984

<LI> A. G. Greenberg and R. E. Ladner, Estimating the Multiplicities of 
Conflicts in Multiple Access Channels (Preliminary Report). Proceedings
of the 24th IEEE Symposium on Foundations of Computer Science, November, 1983.
Later revised and published

<LI> U. Manber and R. E. Ladner, Concurrency Control in a Dynamic Search 
Structure. Proceedings of 
ACM SIGACT-SIGMOD Symposium on Principles of Database Systems,
1982.  Later revised and published

<LI> V. Klee and R. E. Ladner, Qualitative Matrices: Strong Sign-solvability
and Weak Satisfiability. Proceedings of 
First Symposium on Computer-Assisted Analysis
and Model Simplification, 1980.  
Published in <EM> Computer-Assisted Analysis
and Model Simplification</EM>, edited by H. J. Greenberg and J. S. Maybee,
Academic Press, 1981, 293-320

<LI> R. E. Ladner, Complexity Theory with Emphasis on the
Complexity of Logical Theories. Proceedings of Logic Colloquium '79.
Published in <EM> Recursion Theory:
its Generalizations and Applications</EM>, edited by F. R. Drake
and S. S. Wainer, Cambridge University Press, 1980, 286-319

<LI> R. E. Ladner, The Complexity of Problems in Systems of
Communicating Sequential Processes. Proceedings of Eleventh Annual ACM Symposium
on Theory of Computing, l979, 214-223.  Later revised and published

<LI> R. E. Ladner, R. J. Lipton, L. J. Stockmeyer, Alternating
Pushdown Automata. Proceedings of Nineteenth Annual Symposium 
on Foundations of Computer Science, 1978, 92-106.  Later revised 
and published
as ``Alternating Pushdown and Stack Automata''

<LI> G. B. Goodrich, R. E. Ladner, and M. J. Fischer, Straight-line
Programs to Compute Finite Languages. Proceedings of Conference 
on Theoretical Computer Science, University of Waterloo, 1977.  Also
available as Technical Report 77-06-01, Dept. of Computer Science,
University of Washington, 1977

<LI> R. E. Ladner and M. J. Fischer, Parallel Prefix Computation.
Proceedings of 1977 International Conference on Parallel 
Processing, 218-223. Later revised and published

<LI> M. J. Fischer and R. E. Ladner, Propositional Modal Logic
of Programs:  Extended Abstract. Proceedings of Ninth Annual ACM 
Symposium on Theory of Computing 1977, 286-294.  Later revised and
published as ``Propositional Dynamic Logic of Regular Programs''

<LI> R. E. Ladner, N. A. Lynch, and A. R. Selman, Comparison of
Polynomial-time Reducibilities. Proceedings of Sixth Annual ACM 
Symposium on Theory of Computing 1974, 110-121.  Later revised 
and published as `` A Comparison of Polynomial Time Reducibilities''

<LI> R. E. Ladner, Polynomial Time Reducibility. Proceedings of Fifth
Annual ACM Symposium on Theory of Computing 1973, 122-129. Later
revised and published as ``On the Structure of Polynomial Time 
Reducibilities''
</UL>

<H3>
Other Papers
</H3>
<UL>
<LI> C. L. Cheung and R.E. Ladner. Symmetric K-Span Matching Problem.
<EM> Journal of Undergraduate Research</EM> Vol. 2. No. 2., 1995, 168-178.

<LI> E.W. Felten, A. LaMarca, and R. Ladner. Building
Counting Networks from Larger Balancers.  
Technical Report 93-04-09,
Department of Computer Science and Engineering, University of Washington.
Submitted for publication.

<LI> D. McHale and R.E. Ladner. A Simple Algorithm for Automated
Braille Translation.

<LI> G. Swart and R. E. Ladner,
Efficient Algorithms for Reporting Intersections.
Technical Report 83-07-03, Dept. of Computer Science, University of
Washington, 1983

<LI> M. J. Fischer and R. E. Ladner, Data Structures for
Efficient Implementation of Sticky Pointers. Technical Report
79-06-08, Dept. of Computer Science, University of Washington, 1979

<LI> R. E. Ladner, Making Infinite Structures Appear Finite in
First Order Logic. Technical Report 76-10-09, Dept. of Computer
Science, University of Washington, 1976

<LI> R. E. Ladner, The Circuit Value Problem is Log Space Complete
for P. SIGACT NEWS, vol. 7, no. 1, January 1975, 18-20
</UL>
</body>
</html>